package cn.edu.zufe.mjt.recursion;

import java.util.ArrayList;

/**
 * 给定一个n *n的二维网格，从起点(sx，sy)出发，每次可以向上、下、左、右移动一步，最多走k步问有多少种不同的路径可以到达终点(ex，ey)。
 * 例如，一个2*2的网格，起点是(1，1)，终点是(2，2)，最多走2步
 */
public class PathTwo {

    public static int count = 0;
    public static void main(String[] args) {
        pathCount(1, 1, 2, 2, 2, 2);
        System.out.println("paths = " + count);
    }

    /**
     * 为什么用递归?
     * ·每一步的选择(上下左右)将问题分解为更小的子问题。
     * ·每一步移动的选择会影响后续的路径，非常适合用递归来逐层分解
     */
    public static void pathCount(int x, int y, int k, int n, int ex, int ey) {
        // 终止条件
        // 1、if x == ex && y == ey  countPath+=1  到达终点，路径加1
        // 2、if count > k  超过最大步数，返回

        // 递归调用
        // if newX ≥ 1 && newX ≤ n && newY ≥ 1 && newY ≤ n  移动后仍在网格内，递归调用
        // dfs(newX, newY, count+1, n, ex, ey, k)

        // 定义四个方向
        ArrayList<int[]> directions = new ArrayList<>();
        directions.add(new int[]{0, 1});
        directions.add(new int[]{0, -1});
        directions.add(new int[]{1, 0});
        directions.add(new int[]{-1, 0});

        int steps = 0;
        dfs(x,y,ex,ey,steps,n,k,directions);
    }

    private static void dfs(int x, int y, int ex, int ey, int steps, int n, int k, ArrayList<int[]> directions) {
        if (x == ex && y == ey) {
            count++;
        }
        if (steps == k) {
            return ;
        }
        for (int[] direction : directions) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            if (newX >= 1 && newX <= n && newY >= 1 && newY <= n) {
                dfs(newX, newY, ex, ey, steps + 1, n, k, directions);
            }
        }
    }
}
